package hh.leecode.binarytree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 前序遍历二叉树： 中间节点先，再左，再右
 */
public class 二叉树_前序遍历 {
    public static void main(String[] args) {

        TreeNode root = TreeNode.createDefaultTree(1);
        ArrayList<Object> list = new ArrayList<>();
        preorderStack(root, list);
        System.out.println(list);
    }



    /**
     * 递归法
     */
    // 中间节点先，再左，再右
    private static void preorderRecursion(TreeNode root, List<Object> list) {
        if (root == null) return;

        list.add(root.val);
        if (root.left != null) preorderRecursion(root.left, list);
        if (root.right != null) preorderRecursion(root.right, list);

    }


    /**
     * 循环法
     */
    private static void preorderStack(TreeNode root, List<Object> list) {
        if (root == null) return;

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            list.add(pop.val);

            if (pop.right != null) stack.push(pop.right);
            if (pop.left != null) stack.push(pop.left);
        }

    }
}
